package heap;

import java.util.Arrays;

//完全二叉树的数组表示
public class WhatIsHeap {
    public static void main(String[] args) {

        //arr[i]>=arr[2*i],arr[i]>=2*i+1
       // int arr[] = new int[]{12, 15, 13, 5, 7, 25, 18, 20, 10};
        int arr[] = new int[]{123, 12, 31, 23, 123, 12, 31, 2, 43, 523, 45, 234, 52, 34, 524};

        System.out.println(Arrays.toString(arr));

    }


    public void makeMaxHeap(int[] arr){

        // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
        //length/2-1是第一个非叶节点，此处"/"为整除
        for (int i = arr.length / 2 - 1; i >= 0; --i) {

            // 根节点的值
            int nTemp = arr[i];

            // 子结点的位置=2*（父结点位置）+ 1
            int nChild = 2 * i + 1;

            // 得到子结点中较大的结点
            if (nChild < arr.length - 1 && arr[nChild + 1] > arr[nChild])
                ++nChild;

            // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
            if (nTemp < arr[nChild]) {
                arr[i] = arr[nChild];
                arr[nChild] = nTemp;
            }
        }
    }





}
